#include <stdio.h>

void FastSort(int *a,int start,int end)   //O(nlogn)
{
    if(start >= end)
    return;
    int temp = a[start];
    int left = start;
    int right = end;

    while(left < right)
    {
        while(left < right && a[right] > temp)
        {
            right--;   // 不能一直减，会跳出外循环
        }
        if(left < right)
        {
            a[left] = a[right];
            left++;
        }

        while(left < right && a[left] <  temp)
        {
            left++;
        }

        if(left < right)
        {
            a[right] = a[left];
            right--;
        }
    }
    a[left] = temp;
    //递归排序
    FastSort(a,start,left-1);
    FastSort(a,right+1,end);
}

int FindElementByIndex(int *a,int len,int target)
{
    for(int i = 0; i < len; i++)
    {
        if(a[i] == target)
        return i;
    }
    return -1;
}

//二分查找   O(logn)
int BinaryFind(int *a,int len,int target)
{
    int left = 0;
    int right = len-1;
    while(left <= right)
    {
        int mid = left + (right - left) / 2;
        if(a[mid] == target)
            return mid;
        if(a[mid] > target)
            right = mid-1;
        if(a[mid] < target)
            left = mid + 1;
    }
    return -1;
}

void PrintArray(int *a,int len)
{
    for(int i = 0; i < len; i++)
    {
        printf("%d ",a[i]);
    }
    printf("\n");
}

int main()
{
    int a[]= {9,5,14,10,6};
    FastSort(a, 0, sizeof(a)/4);
    PrintArray(a,sizeof(a)/4);
    return 0;
}